//1.迭代--从前往后---空间复杂度O(1)
class Solution {
public:

    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode* first = head;
        ListNode* second = head->next;
        
        ListNode nummpy(-1);
        ListNode* prev = &nummpy;
        prev->next = head;
        while(first && second) {
      
            first->next = second->next;
            second->next = first;
            prev->next = second;
            prev = first;        
            first = prev->next;
            if(first)
                second=first->next;
        }
        return nummpy.next;
    }
};

//2.递归--从后往前---空间复杂度O(n)
class Solution {
public:

    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode* next_head = head->next;
        ListNode* temp = swapPairs(next_head->next);
        head->next = temp;
        next_head->next = head;
        return next_head;
    }
};


//3.通俗易懂的递归理解！！！！！
class Solution {
    public ListNode swapPairs(ListNode head) {
        /*
        递归法:
        宗旨就是紧紧抓住原来的函数究竟返回的是什么?作用是什么即可
        其余的细枝末节不要细究,编译器会帮我们自动完成
         */
        // base case
        if (head == null || head.next == null) return head;
        
        // swapPairs(ListNode head) 的意义就是两两翻转链表中的节点+返回翻转后的新的头结点
        // 我们知道翻转后新的头结点必然是第二个节点
        // 举例子:1->2->3->4 翻转后:2->1->4->3
        ListNode newHead = head.next; // 2
        // 此时tmpHead为:4->3
        ListNode tmpHead = swapPairs(newHead.next);
        // 而前面的还粘连着:1->2->(3)  4->3
        // 此时再让1->4 此时链表为:2->(3) 1->4->3
        head.next = tmpHead;
        // 再将2指向1即可 此时链表为:2->1->4->3 已经完成翻转
        newHead.next = head;
        // 返回新的头结点
        return newHead;
    }
}


